/**
 * 验证二叉树
 *https://leetcode.cn/problems/validate-binary-tree-nodes/submissions/
 * 二叉树上有 n个节点，按从0到 n - 1编号，其中节点i的两个子节点分别是leftChild[i]和rightChild[i]。
 * 只有 所有 节点能够形成且 只 形成 一颗有效的二叉树时，返回true；否则返回 false。
 * 如果节i没有左子节点，那么leftChild[i]就等于-1。右子节点也符合该规则。
 * 注意：节点没有值，本问题中仅仅使用节点编号。
 *
 *
 */
class ValidateBinaryTreeNodes {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
         int[] in=new int[n];//记录每个节点的入度
        for (int i = 0; i <n ; i++) {
            if (leftChild[i]!=-1)
                in[leftChild[i]]++;
            if (rightChild[i]!=-1)
                in[rightChild[i]]++;
        }
        int root=-1;//看看根节点是哪个
        for (int i = 0; i <n ; i++) {
            if (in[i]==0){
                root=i;
                break;
            }
        }
        if (root==-1){
            //没有入度为0的   也就是没有根节点
            return false;
        }
        //开始广搜
        Queue<Integer> queue=new LinkedList<>();
        Set<Integer> set=new HashSet<>();//记录访问过的节点  如果有重复说明不是二叉树
        queue.offer(root);
        set.add(root);
        while (!queue.isEmpty()){
            int temp=queue.poll();
            if (leftChild[temp]!=-1){
                //左子树不为空
                if (set.contains(leftChild[temp])){
                    //左子节点 被访问过
                    return false;
                }
                queue.offer(leftChild[temp]);
                set.add(leftChild[temp]);
            }
            if (rightChild[temp]!=-1){
                //右子树不为空
                if (set.contains(rightChild[temp])){
                    //有子节点 被访问过
                    return false;
                }
                queue.offer(rightChild[temp]);
                set.add(rightChild[temp]);
            }
        }
        //如果set里节点数量就为n那么说明全部节点被访问    因为上面有重复的已经判断了  只剩下没访问的没判断
        return set.size()==n;
    }
}